package com.example.interview.algorithm;

import java.util.regex.Matcher;

/**
 * 输入两棵二叉树A 和B，判断B 是不是A 的子结构。
 * 
 * @Description: TODO
 * @author gaobing
 * @date 2018年10月10日 下午4:32:23 思路：要查找树A 中是否存在和树B 结构一样的子树，我们可以分成两步： 第一步在树A 中找到和B
 *       的根结点的值一样的结点R， 第二步再判断树A 中以R 为根结点的子树是不是包含和树B 一样的结构。
 */
public class Test18BinaryTree {

	/**
	 * 二叉树的树结点
	 * 
	 * @Description: TODO
	 * @author gaobing
	 * @date 2018年10月10日 下午4:34:02
	 *
	 */
	public static class BinaryTreeNode {
		int value;
		BinaryTreeNode left;
		BinaryTreeNode right;
	}

	/**
	 * 
	 * @param root1
	 *            树A的根节点
	 * @param root2
	 *            树B的根节点
	 * @return
	 */
	public static boolean hasSubtree(BinaryTreeNode root1, BinaryTreeNode root2) {
		// 只要两个对象是同一个就返回true
		if (root1 == root2) {
			return true;
		}
		if (root2 == null) {
			return true;
		}
		if (root1 == null) {
			return false;
		}

		// 记录匹配结果
		boolean result = false;
		// 如果节点相等就调用匹配方法
		if (root1.value == root2.value) {
			result = match(root1, root2);
		}
		//
		if (result) {
			return true;
		}

		// 如果不匹配就找树A的左子节点 和右子节点进行判断
		return hasSubtree(root1.left, root2) || hasSubtree(root1.right, root2);

	}

	/**
	 * 从树A根节点root1和树B根节点root2开始，一个一个元素进行判断，判断B是不是A的子结构
	 * 
	 * @param root1
	 *            树A开始匹配的根节点
	 * @param root2
	 *            树B开始匹配的根节点
	 * @return
	 */
	private static boolean match(BinaryTreeNode root1, BinaryTreeNode root2) {
		// 只要两个对象是同一个就返回true
		if (root1 == root2) {
			return true;
		}
		// 只要树B的跟节点为空就返回true
		if (root2 == null) {
			return true;
		}
		// 只要树A 的根节点是空返回false
		if (root1 == null) {
			return false;
		}

		// 如果两个跟节点相等，则分别判断左子节点 和右子节点
		if (root1.value == root2.value) {
			return match(root1.left, root2.left) && match(root1.right, root2.right);
		}

		// 终节点值不相等，返回false
		return false;
	}

	public static void main(String[] args) {
		BinaryTreeNode root1 = new BinaryTreeNode();
		root1.value = 8;
		root1.right = new BinaryTreeNode();
		root1.right.value = 7;
		root1.left = new BinaryTreeNode();
		root1.left.value = 8;
		root1.left.left = new BinaryTreeNode();
		root1.left.left.value = 9;
		root1.left.right = new BinaryTreeNode();
		root1.left.right.value = 2;
		root1.left.right.left = new BinaryTreeNode();
		root1.left.right.left.left = new BinaryTreeNode();
		root1.left.right.left.left.value = 4;
		root1.left.right.left.right = new BinaryTreeNode();
		root1.left.right.left.right.value = 7;

		BinaryTreeNode root2 = new BinaryTreeNode();
		root2.value = 8;
		root2.left = new BinaryTreeNode();
		root2.left.value = 9;
		root2.right = new BinaryTreeNode();
		root2.right.value = 2;

		System.out.println(hasSubtree(root1, root2));
		System.out.println(hasSubtree(root2, root1));
		System.out.println(hasSubtree(root1, root1.left));
		System.out.println(hasSubtree(root1, null));
		System.out.println(hasSubtree(null, root2));
		System.out.println(hasSubtree(null, null));
	}

}
